import java.util.*;

/**
 * 题目：万能字符单词拼写
 * 
 * 题目描述：
 * 有一个字符串数组words和一个字符串chars。
 * 假如可以用chars中的字母拼写出words中的某个"单词"(字符串)，那么我们就认为你掌握了这个单词。
 * words的字符仅由a-z 英文小写字母组成。例如:abc
 * chars 由 a-z 英文小写字母和"?"组成。其中英文问号"?"表示万能字符，能够在拼写时当做任意一个英文字母。例如:"?"可以当做"a"等字母。
 * **注意:** 每次拼写时，chars中的每个字母和万能字符都只能使用一次。
 * 输出词汇表words中你掌握的所有单词的个数。没有掌握任何单词，则输出0。
 * 
 * 输入描述：
 * 1. 第1行输入数组words的个数，记为N。
 * 2. 从第2行开始到第N+1行依次输入数组words的每个字符串元素。
 * 3. 第N+2行输入字符串chars。
 * 
 * 输出描述：
 * 输出一个整数，表示词汇表words中你掌握的单词个数。
 * 
 * 示例1：
 * 输入：
 * 4
 * cat
 * bt
 * hat
 * tree
 * atach??
 * 输出：
 * 3
 * 
 * 解题思路：
 * 本题的核心是判断一个单词是否可以使用给定字符集（包含万能字符）来拼写，且每个字符只能使用一次。
 * 这可以通过统计字符频率来高效解决。
 * 
 * 算法分析：
 * - 时间复杂度：O(L_chars + N * L_word)
 * - 空间复杂度：O(1) (对于固定大小的字母表)
 * - 算法类型：字符频率统计，贪心匹配
 */
public class UniversalCharacterWordSpelling {
    
    /**
     * 方法1：数组计数法（推荐使用）
     * 使用固定大小的数组来统计字符频率，效率最高
     * 
     * 算法思路：
     * 1. 使用长度为27的数组（26个字母 + 1个万能字符）
     * 2. 统计chars中每个字符的出现次数
     * 3. 对每个单词，复制频率数组并尝试匹配
     * 
     * 时间复杂度：O(L_chars + N * L_word)
     * 空间复杂度：O(1)
     */
    public static int countWords1(String[] words, String chars) {
        int[] charCount = new int[27]; // 0-25: a-z, 26: ?
        int wildcardCount = 0;
        
        // 统计chars中的字符频率
        for (char c : chars.toCharArray()) {
            if (c == '?') {
                wildcardCount++;
            } else {
                charCount[c - 'a']++;
            }
        }
        
        int masteredCount = 0;
        
        // 检查每个单词
        for (String word : words) {
            int[] tempCount = charCount.clone();
            int tempWildcard = wildcardCount;
            boolean canSpell = true;
            
            for (char c : word.toCharArray()) {
                if (tempCount[c - 'a'] > 0) {
                    tempCount[c - 'a']--; // 使用普通字符
                } else if (tempWildcard > 0) {
                    tempWildcard--; // 使用万能字符
                } else {
                    canSpell = false;
                    break;
                }
            }
            
            if (canSpell) {
                masteredCount++;
            }
        }
        
        return masteredCount;
    }
    
    /**
     * 方法2：HashMap计数法
     * 使用HashMap来统计字符频率，更灵活但稍慢
     * 
     * 算法思路：
     * 1. 使用HashMap统计chars中每个字符的出现次数
     * 2. 对每个单词，复制HashMap并尝试匹配
     * 
     * 时间复杂度：O(L_chars + N * L_word)
     * 空间复杂度：O(K) K为不同字符的数量
     */
    public static int countWords2(String[] words, String chars) {
        Map<Character, Integer> charCount = new HashMap<>();
        int wildcardCount = 0;
        
        // 统计chars中的字符频率
        for (char c : chars.toCharArray()) {
            if (c == '?') {
                wildcardCount++;
            } else {
                charCount.put(c, charCount.getOrDefault(c, 0) + 1);
            }
        }
        
        int masteredCount = 0;
        
        // 检查每个单词
        for (String word : words) {
            Map<Character, Integer> tempCount = new HashMap<>(charCount);
            int tempWildcard = wildcardCount;
            boolean canSpell = true;
            
            for (char c : word.toCharArray()) {
                if (tempCount.getOrDefault(c, 0) > 0) {
                    tempCount.put(c, tempCount.get(c) - 1);
                } else if (tempWildcard > 0) {
                    tempWildcard--;
                } else {
                    canSpell = false;
                    break;
                }
            }
            
            if (canSpell) {
                masteredCount++;
            }
        }
        
        return masteredCount;
    }
    
    /**
     * 方法3：字符串操作法
     * 直接操作字符串，每次匹配后删除已使用的字符
     * 
     * 算法思路：
     * 1. 将chars转换为StringBuilder以便删除操作
     * 2. 对每个单词，尝试在chars中找到匹配的字符并删除
     * 
     * 时间复杂度：O(N * L_word * L_chars)
     * 空间复杂度：O(L_chars)
     */
    public static int countWords3(String[] words, String chars) {
        int masteredCount = 0;
        
        for (String word : words) {
            StringBuilder availableChars = new StringBuilder(chars);
            boolean canSpell = true;
            
            for (char c : word.toCharArray()) {
                int index = availableChars.indexOf(String.valueOf(c));
                if (index != -1) {
                    availableChars.deleteCharAt(index); // 删除已使用的字符
                } else {
                    int wildcardIndex = availableChars.indexOf("?");
                    if (wildcardIndex != -1) {
                        availableChars.deleteCharAt(wildcardIndex); // 删除万能字符
                    } else {
                        canSpell = false;
                        break;
                    }
                }
            }
            
            if (canSpell) {
                masteredCount++;
            }
        }
        
        return masteredCount;
    }
    
    /**
     * 方法4：位运算优化法
     * 使用位运算来优化字符匹配过程
     * 
     * 算法思路：
     * 1. 使用位掩码来表示字符的存在性
     * 2. 通过位运算快速判断字符是否可用
     * 
     * 时间复杂度：O(L_chars + N * L_word)
     * 空间复杂度：O(1)
     */
    public static int countWords4(String[] words, String chars) {
        int[] charCount = new int[26];
        int wildcardCount = 0;
        
        // 统计chars中的字符频率
        for (char c : chars.toCharArray()) {
            if (c == '?') {
                wildcardCount++;
            } else {
                charCount[c - 'a']++;
            }
        }
        
        int masteredCount = 0;
        
        // 检查每个单词
        for (String word : words) {
            int[] tempCount = Arrays.copyOf(charCount, 26);
            int tempWildcard = wildcardCount;
            boolean canSpell = true;
            
            for (char c : word.toCharArray()) {
                if (tempCount[c - 'a'] > 0) {
                    tempCount[c - 'a']--;
                } else if (tempWildcard > 0) {
                    tempWildcard--;
                } else {
                    canSpell = false;
                    break;
                }
            }
            
            if (canSpell) {
                masteredCount++;
            }
        }
        
        return masteredCount;
    }
    
    /**
     * 方法5：递归回溯法
     * 使用递归回溯来尝试所有可能的字符匹配组合
     * 
     * 算法思路：
     * 1. 对每个单词，使用递归回溯尝试匹配
     * 2. 优先使用普通字符，再使用万能字符
     * 
     * 时间复杂度：O(N * 2^L_word) 最坏情况
     * 空间复杂度：O(L_word) 递归栈深度
     */
    public static int countWords5(String[] words, String chars) {
        int[] charCount = new int[26];
        int wildcardCount = 0;
        
        // 统计chars中的字符频率
        for (char c : chars.toCharArray()) {
            if (c == '?') {
                wildcardCount++;
            } else {
                charCount[c - 'a']++;
            }
        }
        
        int masteredCount = 0;
        
        // 检查每个单词
        for (String word : words) {
            if (canSpellRecursive(word, 0, charCount.clone(), wildcardCount)) {
                masteredCount++;
            }
        }
        
        return masteredCount;
    }
    
    /**
     * 递归辅助方法：判断单词是否可以从指定位置开始拼写
     */
    private static boolean canSpellRecursive(String word, int index, int[] charCount, int wildcardCount) {
        if (index == word.length()) {
            return true; // 所有字符都匹配成功
        }
        
        char c = word.charAt(index);
        
        // 尝试使用普通字符
        if (charCount[c - 'a'] > 0) {
            charCount[c - 'a']--;
            if (canSpellRecursive(word, index + 1, charCount, wildcardCount)) {
                return true;
            }
            charCount[c - 'a']++; // 回溯
        }
        
        // 尝试使用万能字符
        if (wildcardCount > 0) {
            if (canSpellRecursive(word, index + 1, charCount, wildcardCount - 1)) {
                return true;
            }
        }
        
        return false;
    }
    
    /**
     * 主方法 - 程序入口
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        System.out.println("请输入单词个数N：");
        int n = scanner.nextInt();
        scanner.nextLine(); // 消费换行符
        
        String[] words = new String[n];
        System.out.println("请输入" + n + "个单词：");
        for (int i = 0; i < n; i++) {
            words[i] = scanner.nextLine();
        }
        
        System.out.println("请输入字符集chars：");
        String chars = scanner.nextLine();
        
        // 测试所有方法
        System.out.println("\n=== 所有算法结果对比 ===");
        System.out.println("方法1（数组计数法）: " + countWords1(words, chars));
        System.out.println("方法2（HashMap计数法）: " + countWords2(words, chars));
        System.out.println("方法3（字符串操作法）: " + countWords3(words, chars));
        System.out.println("方法4（位运算优化法）: " + countWords4(words, chars));
        System.out.println("方法5（递归回溯法）: " + countWords5(words, chars));
        
        // 推荐使用的方法
        System.out.println("\n推荐使用方法1（数组计数法），时间复杂度最优：O(L_chars + N * L_word)");
        
        scanner.close();
    }
}
